package com.shm.leetcode;

import java.util.Arrays;

/**
 * 60. 第k个排列
 * 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
 *
 * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 *
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * 给定 n 和 k，返回第 k 个排列。
 *
 * 说明：
 *
 * 给定 n 的范围是 [1, 9]。
 * 给定 k 的范围是[1,  n!]。
 * 示例 1:
 *
 * 输入: n = 3, k = 3
 * 输出: "213"
 * 示例 2:
 *
 * 输入: n = 4, k = 9
 * 输出: "2314"
 * @author SHM
 */
public class GetPermutation {
    public String getPermutation(int n, int k) {
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i-1]*i;
        }

        --k;
        StringBuffer stringBuffer = new StringBuffer();
        int[] valid = new int[n+1];
        Arrays.fill(valid,1);
        for (int i = 1; i <= n; i++) {
            int order = k/factorial[n-i] + 1;
            for (int j = 1; j <= n; j++) {
                order-=valid[j];
                if(order==0){
                    stringBuffer.append(j);
                    valid[j]=0;
                    break;
                }
            }
            k%=factorial[n-i];
        }
        return stringBuffer.toString();
    }


    int n;
    int k;

    /**
     * 基于以下几点考虑：
     *
     * 所求排列 一定在叶子结点处得到，进入每一个分支，可以根据已经选定的数的个数，进而计算还未选定的数的个数，然后计算阶乘，就知道这一个分支的 叶子结点 的个数：
     * 如果 kk 大于这一个分支将要产生的叶子结点数，直接跳过这个分支，这个操作叫「剪枝」；
     * 如果 kk 小于等于这一个分支将要产生的叶子结点数，那说明所求的全排列一定在这一个分支将要产生的叶子结点里，需要递归求解。
     *
     *
     * 下面以示例 2：输入: n = 4n=4，k = 9k=9，介绍如何使用「回溯 + 剪枝」的思想得到输出 "2314"。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/problems/permutation-sequence/solution/hui-su-jian-zhi-python-dai-ma-java-dai-ma-by-liwei/
     * @param n
     * @param k
     * @return
     */
    public String getPermutation_2(int n, int k) {
        this.n = n;
        this.k = k;
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        StringBuffer ans = new StringBuffer();
        boolean[] used = new boolean[n+1];
        Arrays.fill(used,false);
        dfs(0,ans,used,factorial);
        return ans.toString();
    }

    public void dfs(int index,StringBuffer ans,boolean[] used,int[] factorial){
        if (index==n){
            return;
        }
        // 计算还未确定的数字的全排列的个数，第 1 次进入的时候是 n - 1
        int cnt = factorial[n-1-index];
        for (int i = 1; i <= n; i++) {
            if (used[i]){
                continue;
            }
            if (cnt<k){
                k-=cnt;
                continue;
            }
            ans.append(i);
            used[i] = true;
            dfs(index+1,ans,used,factorial);
            // 注意 1：没有回溯（状态重置）的必要

            // 注意 2：这里要加 return，后面的数没有必要遍历去尝试了
            return;
        }
    }

    public String getPermutation_3(int n, int k) {
        final int[] arr = new int[]{1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
        boolean[] visited = new boolean[n + 1];
        Arrays.fill(visited, false);
        StringBuilder permutation = new StringBuilder();
        for (int i=n-1;i>=0;i--){
            int cnt = arr[i];
            for (int j = 1; j <= n; j++) {
                if (visited[j]){
                    continue;
                }
                if (k>cnt){
                    k-=cnt;
                    continue;
                }
                permutation.append(j);
                visited[j] = true;
                break;
            }
        }
        return permutation.toString();
    }
}
